﻿using System.Collections;
using System.Collections.Generic;
using UnityEngine;
//此类非原创，网站 https://zhuanlan.zhihu.com/p/112849816 拷贝过来的

public class AStarPath
{
    public class AStarNode
    {
        public int G;//与初始值的优先值
        public int H;//与目的地的优先值
        public MapItem Data;
        public AStarNode LastNode;

        public int GetF()
        {
            return G + H;
        }
    }

    /// <summary>
    /// A星寻路
    /// </summary>
    /// <param name="startItem">起始地</param>
    /// <param name="endItem">目的地</param>
    /// <param name="AllPath">地图数据</param>
    /// <param name="ShortestPath">输出的路径</param>
    /// <returns>是否可到达</returns>
    public static bool ComputePath(MapItem startItem, MapItem endItem,
        List<MapItem> AllPath, out List<MapItem> ShortestPath)
    {

        bool finded = false;

        ShortestPath = new List<MapItem>();
        List<AStarNode> OpenedNodes = new List<AStarNode>();
        List<AStarNode> ClosedNodes = new List<AStarNode>();//close 列表已经检查过
        List<AStarNode> CurrentPaths = new List<AStarNode>();

        AStarNode Current = new AStarNode() { Data = startItem };
        OpenedNodes.Add(Current);

        while (OpenedNodes.Count > 0 && !finded)
        {
            Current = GetOpenedBest(OpenedNodes);
            OpenedNodes.Remove(Current);
            ClosedNodes.Add(Current);
            //周围6个 加入到Opened
            //遍历相邻的上下四个 取最近的
            int currentX = Current.Data.x;
            int currentY = Current.Data.y;
            int isDoubleRaw = currentY % 2;

            //如果是奇数行 上下两行0,1相邻；偶数行 上下两行-1,0相邻
            //当前节点的所有出口
            //todo 这里需要优化：不每次new出来
            Vector2[] points = new Vector2[]
            {
                new Vector2(currentX+isDoubleRaw-1, currentY+1),
                new Vector2(currentX+isDoubleRaw, currentY+1),
                new Vector2(currentX+isDoubleRaw-1, currentY-1),
                new Vector2(currentX+isDoubleRaw, currentY-1),
                new Vector2(currentX-1, currentY),
                new Vector2(currentX+1, currentY),
            };

            //不在closed列表中的，不在opened列表中的 ， 可以通行的，  添加到opened列表中
            for (int i = 0; i < points.Length; i++)
            {
                var item = GetMapItem(points[i], AllPath);
                if (item != null && !Contains(item, ClosedNodes) && item.CanThrough())
                {
                    int G = Current.G + 1;
                    int H = Mathf.Abs(item.x - endItem.x) +
                            Mathf.Abs(item.y - endItem.y);

                    if (Contains(item, OpenedNodes))//这个节点已经在打开列表中了  计算权重保留更优的
                    {
                        AStarNode ExistingNode = GetNode(item, OpenedNodes);
                        if (ExistingNode.GetF() > G + H)//新的节点更优 更新节点
                        {
                            ExistingNode.LastNode = Current;
                            ExistingNode.G = G;
                            ExistingNode.H = H;
                        }
                        else//老节点更优  不动
                        {

                        }
                    }
                    else
                    {
                        //将节点加入到打开列表
                        AStarNode cnode = new AStarNode();
                        cnode.Data = item;
                        cnode.LastNode = Current;
                        cnode.G = G;
                        cnode.H = H;
                        OpenedNodes.Add(cnode);

                        if (item == endItem)
                        {
                            finded = true; break;//目的节点
                        }
                    }
                }

            }
        }

        if (finded)
        {
            Current = OpenedNodes[OpenedNodes.Count - 1];
            do
            {
                ShortestPath.Insert(0, Current.Data);
                Current = Current.LastNode;
            } while (Current.LastNode != null);

        }

        return finded;
    }

    //在打开列表中找到一个最优的节点
    static AStarNode GetOpenedBest(List<AStarNode> OpenedNodes)
    {
        AStarNode target = OpenedNodes[0];
        for (int i = 1; i < OpenedNodes.Count; i++)
        {
            if (OpenedNodes[i].GetF() < target.GetF())
            {
                target = OpenedNodes[i];
            }
        }

        return target;
    }

    //todo 这里需要优化：不能每次遍历
    static bool Contains(MapItem item, List<AStarNode> nodes)
    {
        for (int i = 0; i < nodes.Count; i++)
        {
            if (nodes[i].Data == item)
                return true;
        }
        return false;
    }

    //todo 这里需要优化：不能每次遍历
    static AStarNode GetNode(MapItem item, List<AStarNode> nodes)
    {
        for (int i = 0; i < nodes.Count; i++)
        {
            if (nodes[i].Data == item)
                return nodes[i];
        }
        return null;
    }

    static MapItem GetMapItem(Vector2 point, List<MapItem> AllPath)
    {
        for (int i = 0; i < AllPath.Count; i++)
        {
            if (AllPath[i].x == point.x && AllPath[i].y == point.y)
                return AllPath[i];
        }

        return null;
    }
}